Usenet 1993 July/InfoMagic USENET CD-ROM July 1993.ISO/sources/unix/volume19/fbm/part08

Internet Message Format | 1989-06-08 | 27.9 KB

Subject:  v19i054:  FBM, image manipulation library, Part08/08
Newsgroups: comp.sources.unix
Sender: sources
Approved: [e-mail]

Submitted-by: [e-mail]
Posting-number: Volume 19, Issue 54
Archive-name: fbm/part08

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#        "End of archive 8 (of 8)."
# Contents:  fbquant.c
# Wrapped by [e-mail] on Fri Jun  9 08:38:31 1989
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'fbquant.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'fbquant.c'\"
else
echo shar: Extracting \"'fbquant.c'\" \(26110 characters\)
sed "s/^X//" >'fbquant.c' <<'END_OF_FILE'
X/****************************************************************
X * fbquant.c: FBM Library 0.93 (Beta test) 03-May-89  Michael Mauldin
X *
X * Copyright (C) 1989 by Michael Mauldin.  Permission is granted to
X * use this file in whole or in part provided that you do not sell it
X * for profit and that this copyright notice is retained unchanged.
X *
X * fbquant: Convert an RGB color image to mapped color format (color
X *        quantization step).  Floyd-Steinberg dithering is used
X *        to reduce color banding.  The quantization used is a
X *        modification of Heckbert's median cut.
X *
X * USAGE
X *    % fbquant [ -c<numcolors> ] [ -<type> ] < rgb > mapped
X *
X * EDITLOG
X *    LastEditDate = Wed May  3 21:55:36 1989 - Michael Mauldin
X *    LastFileName = /usr2/mlm/src/misc/fbm/fbquant.c
X *
X * HISTORY
X * 03-May-89  Michael Mauldin (mlm) at Carnegie Mellon University
X *    Clear FBM pointers before allocate
X *
X * 07-Apr-89  Michael Mauldin (mlm) at Carnegie Mellon University
X *    Add provision for using colormap from another image.
X *
X * 07-Mar-89  Michael Mauldin (mlm) at Carnegie Mellon University
X *    Beta release (version 0.93) [e-mail]
X *
X * 26-Feb-89  Michael Mauldin (mlm) at Carnegie Mellon University
X *    Changes for small color maps.  Fixed bug with unsigned
X *    arithmetic that ruined dithering for images with small
X *    colormaps.  Added error limiting in the Floyd-Steinberg
X *    code to prevent color "shadowing" that occurs with small
X *    numbers of colors.  Also change to use colors 0..n-1 instead
X *    of reserving colors 0 and n-1 for Sun foreground/background
X *    colors.
X *
X * 11-Nov-88  Michael Mauldin (mlm) at Carnegie Mellon University
X *    Created.
X *
X * References: Uses a variant of Heckbert's adaptive partitioning
X *           algorithm.  See Computer Graphics, v16n3 July 1982
X ****************************************************************/
X
X# include <stdio.h>
X# include "fbm.h"
X
Xint cmp_red(), cmp_grn(), cmp_blu(), cmp_cmap(), cmp_int();
X
X# define RD 0
X# define GR 1
X# define BL 2
X# define REDMASK 0076000
X# define REDSHFT 10
X# define GRNMASK 0001740
X# define GRNSHFT 5
X# define BLUMASK 0000037
X# define BLUSHFT 0
X# define CUBITS  5
X# define CUBIGN  (8-CUBITS)
X# define CUBSID  32
X# define CUBSIZ  32768
X# define MAXSHRT 32767
X# define MAXERR     32
X
X# define GETR(X) (((X) & REDMASK) >> REDSHFT)
X# define GETG(X) (((X) & GRNMASK) >> GRNSHFT)
X# define GETB(X)  ((X) & BLUMASK)
X
X# define CLRINDEX(R,G,B)            \
X    (((R) << REDSHFT) & REDMASK |        \
X     ((G) << GRNSHFT) & GRNMASK |        \
X     ((B)  & BLUMASK))
X
X# define CLRINDEX8(R,G,B)            \
X    (((R) << (REDSHFT-CUBIGN)) & REDMASK |    \
X     ((G) << (GRNSHFT-CUBIGN)) & GRNMASK |    \
X     ((B) >> (CUBIGN))  & BLUMASK)
X
X# define GETR8(X) (((X) & REDMASK) >> (REDSHFT-CUBIGN))
X# define GETG8(X) (((X) & GRNMASK) >> (GRNSHFT-CUBIGN))
X# define GETB8(X) (((X) & BLUMASK) << CUBIGN)
X
Xtypedef struct cstruct {
X    unsigned char rd, gr, bl, indx;
X} COLOR;
X
XCOLOR *cmap = NULL;
X
Xtypedef struct pix_struct {
X    short cnt;
X    short color;
X} PIXEL;
X
Xint debug=0, verbose=0, colors=256, showcolor=0, dither=1;
X
X/****************************************************************
X * main
X ****************************************************************/
X
X# define USAGE "Usage: fbquant [ -c<numcolors> ] [ -<type> ] < rgb > mapped"
X
X#ifndef lint
Xstatic char *fbmid =
X    "$FBM fbquant.c <0.93> 07-Mar-89  (C) 1989 by Michael Mauldin$";
X#endif
X
Xmain (argc, argv)
Xchar *argv[];
X{ FBM input, output, mapimage;    /* Images */
X  int hist[CUBSIZ];        /* Color cube 32x32x32 for histogram */
X  int outtype = DEF_8BIT;    /* Output format desired */
X  char *mapfile = NULL;        /* Name of file to copy map from */
X  register int c;
X
X  /* Clear pointers */
X  input.bm = input.cm = (unsigned char *) NULL;
X  output.bm = output.cm = (unsigned char *) NULL;
X  mapimage.bm = mapimage.cm = (unsigned char *) NULL;
X
X  /* Get the options */
X  while (--argc > 0 && (*++argv)[0] == '-')
X  { while (*++(*argv))
X    { switch (**argv)
X      { case 'c':    colors = atoi (*argv+1); SKIPARG; break;
X        case 'm':    mapfile = *argv+1; SKIPARG; break;
X    case 'n':    dither = 0;
X    case 'd':    debug++; break;
X    case 'D':    showcolor++; break;
X    case 'v':    verbose++; break;
X    case 'A':    outtype = FMT_ATK; break;
X    case 'B':    outtype = FMT_FACE; break;
X    case 'F':    outtype = FMT_FBM; break;
X    case 'G':    outtype = FMT_GIF; break;
X    case 'I':    outtype = FMT_IFF; break;
X    case 'L':    outtype = FMT_LEAF; break;
X    case 'M':    outtype = FMT_MCP; break;
X    case 'P':    outtype = FMT_PBM; break;
X    case 'S':    outtype = FMT_SUN; break;
X    case 'T':    outtype = FMT_TIFF; break;
X    case 'X':    outtype = FMT_X11; break;
X    case 'Z':    outtype = FMT_PCX; break;
X    default:    fprintf (stderr, "%s\n", USAGE);
X            exit (1);
X      }
X    }
X  }
X
X  /* Check arguments */
X  if (colors > 256 || colors < 8)
X  { fprintf (stderr, "fbquant can only handle 8..256 colors\n");
X    exit (1);
X  }
X
X  /* Open file if name given as argument */
X  if (! read_bitmap (&input, (argc > 0) ? argv[0] : (char *) NULL))
X  { exit (1); }
X
X  /* Read colormap from map image (if specified) */
X  if (mapfile != NULL)
X  { if (!read_bitmap (&mapimage, mapfile))
X    { perror (mapfile); exit (1); }
X
X    if (mapimage.hdr.clrlen == 0)
X    { fprintf (stderr, "fbquant: %s: no map\n", mapfile); exit (1); }
X
X    /* Dont care about the map image, just its colormap */
X    free (mapimage.bm); mapimage.bm = NULL;
X
X    colors = mapimage.hdr.clrlen / 3;
X    cmap = (COLOR *) malloc ((unsigned) colors * sizeof (COLOR));
X
X    for (c=0; c<colors; c++)
X    { cmap[c].rd = mapimage.cm[c];
X      cmap[c].gr = mapimage.cm[c+colors];
X      cmap[c].bl = mapimage.cm[c+colors*2];
X      cmap[c].indx = c;
X    }
X
X    fprintf (stderr, "Quantizing \"%s\" [%dx%d] with %d colors from %s\n",
X         input.hdr.title, input.hdr.cols, input.hdr.rows, colors, mapfile);
X  }
X  else
X  { fprintf (stderr, "Quantizing \"%s\" [%dx%d] with %d colors\n",
X         input.hdr.title, input.hdr.cols, input.hdr.rows, colors);
X  }
X
X  if (input.hdr.planes != 3 || input.hdr.bits != 8)
X  { fprintf (stderr, "fbquant can only handle 24bit RGB inputs\n");
X    exit (1);
X  }
X
X  /* Now build header for output bit map */
X  output.hdr = input.hdr;
X  output.hdr.planes = 1;
X  output.hdr.clrlen = 3 * colors;
X
X  /* Allocate space for output */
X  alloc_fbm (&output);
X
X  /* Build colormap by sampling and mcut if not specified */
X  if (mapfile == NULL)
X  {
X    cmap = (COLOR *) malloc ((unsigned) colors * sizeof (COLOR));
X    sample_image (&input, hist);
X    build_colormap (hist, cmap, colors);
X  }
X
X  /* Use Floyd-Steinberg error diffusion to quantize using the new cmap */
X  clr_quantize (&input, &output, cmap, colors);
X
X  /* Write out the result */
X  if (write_bitmap (&output, stdout, outtype))
X  { exit (0); }
X
X  exit (1);
X}
X
X/****************************************************************
X * sample_image:
X ****************************************************************/
X
Xsample_image (image, hist)
XFBM *image;
Xint *hist;
X{ register int i, j;
X  register unsigned char *rp, *gp, *bp;
X  int width = image->hdr.cols, height = image->hdr.rows;
X  int rowlen = image->hdr.rowlen, plnlen = image->hdr.plnlen;
X  int used=0;
X
X  /* Clear the histogram */
X  for (i=0; i<CUBSIZ; i++) hist[i] = 0;
X
X  /* Now count */
X  for (j=0; j<height; j++)
X  { rp = &(image->bm[j*rowlen]);
X    gp = rp+plnlen;
X    bp = gp+plnlen;
X
X    for (i=0; i<width; i++)
X    { if (++hist[ CLRINDEX8 (*rp++, *gp++, *bp++) ] == 1) used++; }
X  }
X
X  if (debug)
X  { fprintf (stderr, "Done counting, used %d colors for %d pixels\n",
X         used, width*height);
X  }
X}
X
X/****************************************************************
X * build_colormap:
X ****************************************************************/
X
X# define SWAP(A,B) (t=A,A=B,B=t)
X
Xbuild_colormap (hist, cmap, colors)
Xint *hist;
XCOLOR *cmap;
Xint colors;
X{ register int i, k;
X  PIXEL box[CUBSIZ];
X  register PIXEL *b;
X  int used=0, t;
X
X  /* Build the first box, encompassing all pixels */
X  for (b=box, i=0; i<CUBSIZ; i++)
X  { b->color = i;
X    k = hist[i];
X    b->cnt = (k > MAXSHRT) ? MAXSHRT : k;
X    b++;
X  }
X
X  /* Move all non-zero count pixels to the front of the list */
X  for (i=0, used=0; i<CUBSIZ; i++)
X  { if (box[i].cnt > 0) box[used++] = box[i]; }
X
X  /*-------- Special case if we didnt need all colors --------*/
X  if (used <= colors)
X  {
X    /* Copy the colors actually found */
X    for (i=0; i<used; i++)
X    { cmap[i].rd = GETR8 (box[i].color);
X      cmap[i].gr = GETG8 (box[i].color);
X      cmap[i].bl = GETB8 (box[i].color);
X    }
X
X    /* Set the rest to WHITE */
X    for (; i<colors; i++)
X    { cmap[i].rd = 255;
X      cmap[i].gr = 255;
X      cmap[i].bl = 255;
X    }
X  }
X
X  else                /* Build sets all colors */
X  { split_box (box, used, 0, colors, cmap); }
X
X  /*----------------------------------------------------------------
X   * Now arrange the colors in the desired order.  Sun convention is that
X   * color 0 is white and color n-1 is black, so we sort by increasing
X   * intensity (why not?) and then swap the lightest and darkest colors
X   */
X
X  /* Now sort 0..n-1 according to increasing intensity */
X  qsort (cmap, colors, sizeof (* cmap), cmp_int);
X
X  /* Make first color lightest and last color darkest */
X  SWAP (cmap[0].rd, cmap[colors-1].rd);
X  SWAP (cmap[0].gr, cmap[colors-1].gr);
X  SWAP (cmap[0].bl, cmap[colors-1].bl);
X
X  /* Set the output indices */
X  for (i=0; i<colors; i++) { cmap[i].indx = i; }
X}
X
X/****************************************************************
X * split_box: Basic recursive part of Heckberts adaptive partitioning
X *          algorithm.
X ****************************************************************/
X
Xsplit_box (box, boxlen, clr, numclr, cmap)
XPIXEL *box;
Xint boxlen, clr, numclr;
XCOLOR *cmap;
X{ int maxv[3], minv[3], numv[3];
X  int pcnt[3][CUBSID];
X  int sbox, snum, split, half, maxdif, dif;
X  register PIXEL *top, *bot;
X  int topw, botw;
X  int red, grn, blu;
X  register int i, c;
X
X  /* If numclr exceeds boxlen, we are in trouble */
X  if (numclr > boxlen)
X  { fprintf (stderr, "boxlen %d is less numclr %d, panic!\n than",
X         boxlen, numclr);
X    fflush (stderr);
X    abort ();
X  }
X
X  /* Base case: only one color, assign the average for this cell */
X  if (numclr <= 1)
X  { red = box_avg_red (box, boxlen);
X    grn = box_avg_grn (box, boxlen);
X    blu = box_avg_blu (box, boxlen);
X
X    /* Map x to x+4, because the histogram maps values to multiples of 8 */
X    cmap[clr].rd = red + 4;
X    cmap[clr].gr = grn + 4;
X    cmap[clr].bl = blu + 4;
X
X    if (debug)
X    { fprintf (stderr, "\t\tassigning color %d  <%d,%d,%d>  (%d)\n",
X           clr, cmap[clr].rd, cmap[clr].gr, cmap[clr].bl,
X           box_weight (box, boxlen));
X    }
X
X    return;
X  }
X
X  /* Gather statistics about the boxes contents */
X  minv[RD] = minv[GR] = minv[BL] = CUBSID;
X  maxv[RD] = maxv[GR] = maxv[BL] = 0;
X  numv[RD] = numv[GR] = numv[BL] = 0;
X  for (i=0; i<CUBSID; i++) { pcnt[RD][i] = pcnt[GR][i] = pcnt[BL][i] = 0; }
X
X  for (i=0; i<boxlen; i++)
X  { c = box[i].color;
X    red = GETR(c); grn = GETG(c); blu = GETB(c);
X
X    if (red < minv[RD]) minv[RD] = red;
X    if (red > maxv[RD]) maxv[RD] = red;
X    if (grn < minv[GR]) minv[GR] = grn;
X    if (grn > maxv[GR]) maxv[GR] = grn;
X    if (blu < minv[BL]) minv[BL] = blu;
X    if (blu > maxv[BL]) maxv[BL] = blu;
X
X    if (++pcnt[RD][red] == 1) numv[RD]++;
X    if (++pcnt[GR][grn] == 1) numv[GR]++;
X    if (++pcnt[BL][blu] == 1) numv[BL]++;
X  }
X
X  /* Special case, boxlen = numclr, just assign each box one color */
X  if (boxlen == numclr)
X  { for (i=0; i<boxlen; i++)
X    { split_box (box+i, 1, clr+i, 1, cmap); }
X    return;
X  }
X
X  /* Pick a dimension to split */
X  split = -1; maxdif = -1;
X
X  if ((dif = (maxv[RD] - minv[RD])) > maxdif) { maxdif = dif; split = RD; }
X  if ((dif = (maxv[GR] - minv[GR])) > maxdif) { maxdif = dif; split = GR; }
X  if ((dif = (maxv[BL] - minv[BL])) > maxdif) { maxdif = dif; split = BL; }
X
X  /* Sort along the chosen dimension */
X  switch (split)
X  { case RD:    qsort (box, boxlen, sizeof (*box), cmp_red); break;
X    case GR:    qsort (box, boxlen, sizeof (*box), cmp_grn); break;
X    case BL:    qsort (box, boxlen, sizeof (*box), cmp_blu); break;
X    default:    fprintf (stderr, "panic in split_box, split = -1\n");
X        fflush (stderr); fflush (stdout); abort ();
X  }
X
X  /*
X   * Split at the median, but make sure there are at least numclr/2
X   * different colors on each side of the split, to avoid wasting
X   * colors.
X   *
X   * Note: need to keep in mind that when the box is large, dont split
X   *       too close to one edge.
X   */
X
X  half = numclr / 2;
X  top = box;        bot = box + (boxlen-1);
X  topw = top->cnt;    botw = bot->cnt;
X
X  /* Set top and bot to point to min/max feasible splits */
X  while ((top-box)+1 < half)        { top++; topw += top->cnt; }
X  while ((boxlen-(bot-box)) < half)    { bot--; botw += bot->cnt; }
X
X  /* Move top and bottom towards each other 1/8 of remaining distance */
X  c = (bot-top) / 8;
X  for (i=0; i<c; i++)            { top++; topw += top->cnt; }
X  for (i=0; i<c; i++)            { bot--; botw += bot->cnt; }
X
X  /* Now search for median */
X  while (top < bot)
X  { if (topw < botw)            { top++; topw += top->cnt; }
X    else                { bot--; botw += bot->cnt; }
X  }
X
X  /* Decide which half gets the midpoint */
X  if (topw > botw)            /* Median wants to go with top */
X  { sbox = (top-box) + 1;
X    snum = numclr - half;
X  }
X  else                    /* Median wants to go with bottom */
X  { sbox = (top - box);
X    snum = half;
X  }
X
X  /* Handle boundary conditions with number of colors vs box size */
X  if (sbox == 0) sbox++;
X  else if (sbox == boxlen) sbox--;
X
X  while (snum > sbox) snum--;
X  while (numclr-snum > boxlen-sbox) snum++;
X
X# ifndef OPTIMIZE
X  /* Check for boundary condition errors */
X  if (snum <= 0 || snum >= numclr)
X  { fprintf (stderr, "panic, using zero colors for box\n");
X    fflush (stderr);
X    abort ();
X  }
X
X  if (boxlen-sbox < numclr-snum)
X  { fprintf (stderr, "panic, about to used %d boxes for %d colors\n",
X         boxlen-sbox, numclr-snum);
X    fflush (stderr);
X    abort ();
X  }
X
X  if (sbox < snum)
X  { fprintf (stderr, "panic, about to used %d boxes for %d colors\n",
X         sbox, snum);
X    fflush (stderr);
X    abort ();
X  }
X# endif
X
X  if (debug)
X  { int count = numclr, depth = 8;
X    while (count > 0) { depth--; count /= 2; }
X    for (i=0; i<depth; i++) fprintf (stderr, "  ");
X
X    fprintf (stderr, "box [%d..%d|%d] r(%d,%d,%d) g(%d,%d,%d) b(%d,%d,%d) =>",
X         0, boxlen-1, numclr,
X         minv[RD], maxv[RD], numv[RD],
X         minv[GR], maxv[GR], numv[GR],
X         minv[BL], maxv[BL], numv[BL]);
X    fprintf (stderr, " %c [%d..%d|%d] [%d..%d|%d]\n",
X         "RGB"[split], 0, sbox-1, snum, sbox, boxlen-1, numclr-snum);
X  }
X
X  /* Now recurse and split each sub-box */
X  split_box (box,      sbox,          clr,      snum,        cmap);
X  split_box (box+sbox, boxlen - sbox, clr+snum, numclr-snum, cmap);
X}
X
X/****************************************************************
X * box_weight: Determine the total count of a box
X ****************************************************************/
X
Xbox_weight (box, boxlen)
Xregister PIXEL *box;
Xregister int boxlen;
X{ register int sum = 0, i;
X
X  for (i=0; i<boxlen; i++)
X  { sum += box[i].cnt; }
X
X  return (sum);
X}
X
X/****************************************************************
X * box_avg_red: Determine the average red value [0..255] of a box
X ****************************************************************/
X
Xbox_avg_red (box, boxlen)
Xregister PIXEL *box;
Xregister int boxlen;
X{ register int sum = 0, n = 0, i;
X
X  for (i=0; i<boxlen; i++)
X  { sum += GETR8(box[i].color); n++; }
X
X  return (sum / n);
X}
X
X/****************************************************************
X * box_avg_grn: Determine the average grn value [0..255] of a box
X ****************************************************************/
X
Xbox_avg_grn (box, boxlen)
Xregister PIXEL *box;
Xregister int boxlen;
X{ register int sum = 0, n = 0, i;
X
X  for (i=0; i<boxlen; i++)
X  { sum += GETG8(box[i].color); n++; }
X
X  return (sum / n);
X}
X
X/****************************************************************
X * box_avg_blu: Determine the average blu value [0..255] of a box
X ****************************************************************/
X
Xbox_avg_blu (box, boxlen)
Xregister PIXEL *box;
Xregister int boxlen;
X{ register int sum = 0, n = 0, i;
X
X  for (i=0; i<boxlen; i++)
X  { sum += GETB8(box[i].color); n++; }
X
X  return (sum / n);
X}
X
X
X/****************************************************************
X * sort by increasing red ( then green and blue )
X ****************************************************************/
X
Xcmp_red (a, b)
XPIXEL *a, *b;
X{ register r;
X
X  if (r = GETR(a->color) - GETR(b->color))
X  { return (r); }
X
X  if (r = GETG(a->color) - GETG(b->color))
X  { return (r); }
X
X  if (r = GETB(a->color) - GETB(b->color))
X  { return (r); }
X
X  return (0);
X}
X
X/****************************************************************
X * sort by increasing green ( then blue and red )
X ****************************************************************/
X
Xcmp_grn (a, b)
XPIXEL *a, *b;
X{ register r;
X
X  if (r = GETG(a->color) - GETG(b->color))
X  { return (r); }
X
X  if (r = GETB(a->color) - GETB(b->color))
X  { return (r); }
X
X  if (r = GETR(a->color) - GETR(b->color))
X  { return (r); }
X
X  return (0);
X}
X
X/****************************************************************
X * sort by increasing blue ( then red and green )
X ****************************************************************/
X
Xcmp_blu (a, b)
XPIXEL *a, *b;
X{ register r;
X
X  if (r = GETB(a->color) - GETB(b->color))
X  { return (r); }
X
X  if (r = GETR(a->color) - GETR(b->color))
X  { return (r); }
X
X  if (r = GETG(a->color) - GETG(b->color))
X  { return (r); }
X
X  return (0);
X}
X
X/****************************************************************
X * clr_quantize: Do Floyd Steinberg quantizing on the image
X ****************************************************************/
X
Xclr_quantize (input, output, cmap, colors)
XFBM *input, *output;
XCOLOR *cmap;
Xint colors;
X{ int **cerr, **lerr, **terr;
X  int width = input->hdr.cols, height = input->hdr.rows;
X  int rowlen = input->hdr.rowlen, plnlen = input->hdr.plnlen;
X  register int i, j;
X  register int rd, gr, bl;
X  int rderr, grerr, blerr, clr;
X  unsigned char *rp, *gp, *bp, *obm;
X
X  /*-------- Copy colormap into output bitmap --------*/
X  for (i=0; i<colors; i++)
X  { output->cm[i]               = cmap[i].rd;
X    output->cm[i+colors]        = cmap[i].gr;
X    output->cm[i+colors+colors] = cmap[i].bl;
X  }
X
X  /*
X   * Precompute necessary nearest neighbor query info.  Note that we wait
X   * until after copying the colormap, since init reorders it
X   */
X
X  init_nearest (cmap, colors);
X
X  /*-------- Do halftoning --------*/
X  cerr = (int **) malloc (3 * sizeof (int *));
X  lerr = (int **) malloc (3 * sizeof (int *));
X  cerr[RD] = (int *) malloc (width * sizeof (int));
X  cerr[GR] = (int *) malloc (width * sizeof (int));
X  cerr[BL] = (int *) malloc (width * sizeof (int));
X  lerr[RD] = (int *) malloc (width * sizeof (int));
X  lerr[GR] = (int *) malloc (width * sizeof (int));
X  lerr[BL] = (int *) malloc (width * sizeof (int));
X
X  /*-------- Just use the nearest color everywhere --------*/
X  if (!dither)
X  {
X    for (j=0; j<height; j++)
X    { rp = &(input->bm[j*rowlen]);
X      gp = rp+plnlen;
X      bp = gp+plnlen;
X      obm = &(output->bm[j*rowlen]);
X
X      for (i=0; i<width; i++)
X      { rd = *rp++; gr = *gp++; bl = *bp++;
X
X        obm[i] = cmap[nearest (rd, gr, bl, cmap, colors)].indx;
X      }
X    }
X
X    return;
X  }
X
X  /*------ Just use the nearest color around the left, right, and top ------*/
X
X  /* Top border */
X  rp = input->bm; gp = rp+plnlen; bp = gp+plnlen;
X  obm = output->bm;
X  for (i=0; i<width; i++)
X  { obm[i] = cmap[nearest (rp[i], gp[i], bp[i], cmap, colors)].indx; }
X
X  /* Left border */
X  rp = input->bm; gp = rp+plnlen; bp = gp+plnlen;
X  obm = output->bm;
X  for (j=0; j<height; j++)
X  { obm[j*rowlen] = cmap[nearest (rp[j*rowlen], gp[j*rowlen],
X             bp[j*rowlen], cmap, colors)].indx; }
X
X  /* Right border */
X  rp = &(input->bm[width-1]); gp = rp + plnlen; bp = gp + plnlen;
X  obm = &(output->bm[width-1]);
X  for (j=0; j<height; j++)
X  { obm[j*rowlen] = cmap[nearest (rp[j*rowlen], gp[j*rowlen],
X                  bp[j*rowlen], cmap, colors)].indx; }
X
X  /*-------- Clear error vectors --------*/
X  for (i=0; i<width; i++)
X  { cerr[RD][i] = cerr[GR][i] = cerr[BL][i] = 0;
X    lerr[RD][i] = lerr[GR][i] = lerr[BL][i] = 0;
X  }
X
X  /*-------- Major loop for Floyd-Steinberg --------*/
X  for (j=1; j<height; j++)
X  { rp = &(input->bm[j*rowlen+1]);
X    gp = rp+plnlen;
X    bp = gp+plnlen;
X    obm = &(output->bm[j*rowlen+1]);
X
X    for (i=1; i<width-1; i++)
X    { rd = *rp++; gr = *gp++; bl = *bp++;
X
X      /* Sum up errors using Floyd-Steinberg weights */
X      rderr= cerr[RD][i-1] + 7*lerr[RD][i-1] + 5*lerr[RD][i] + 3*lerr[RD][i+1];
X      grerr= cerr[GR][i-1] + 7*lerr[GR][i-1] + 5*lerr[GR][i] + 3*lerr[GR][i+1];
X      blerr= cerr[BL][i-1] + 7*lerr[BL][i-1] + 5*lerr[BL][i] + 3*lerr[BL][i+1];
X
X      rderr >>= 4;    /* Divide by 16 */
X      grerr >>= 4;    /* Divide by 16 */
X      blerr >>= 4;    /* Divide by 16 */
X
X      /* Chose nearest color to adjusted RGB value */
X      rd += rderr; gr += grerr; bl += blerr;
X
X      clr = nearest (rd, gr, bl, cmap, colors);
X      *obm++ = cmap[clr].indx;
X
X      /* Compute accumulated error for this pixel */
X      rd -= (int) cmap[clr].rd;
X      gr -= (int) cmap[clr].gr;
X      bl -= (int) cmap[clr].bl;
X
X      /* Limit error (avoids color shadows) */
X      if (rd < -MAXERR || rd > MAXERR)  rd = (rd * 3) >> 2;
X      if (gr < -MAXERR || gr > MAXERR)  gr = (gr * 3) >> 2;
X      if (bl < -MAXERR || bl > MAXERR)  bl = (bl * 3) >> 2;
X
X      /* Store errors in error vectors */
X      cerr[RD][i] = rd;
X      cerr[GR][i] = gr;
X      cerr[BL][i] = bl;
X    }
X
X    /* Swap error vectors */
X    terr = lerr; lerr = cerr; cerr = terr;
X  }
X}
X
X/****************************************************************
X * nearest: Choose nearest color
X ****************************************************************/
X
Xshort cache[CUBSIZ];
X
Xinit_nearest (cmap, colors)
XCOLOR *cmap;
Xint colors;
X{ register int i;
X
X  /* Initialize the cache */
X  for (i=0; i<CUBSIZ; i++) { cache[i] = -1; }
X
X  /* Sort the colormap by decreasing red, then green, then blue */
X  qsort (cmap, colors, sizeof (COLOR), cmp_cmap);
X
X  if (debug || showcolor)
X  { fprintf (stderr, "\nFinal colormap:\n\n");
X    for (i=0; i<colors; i++)
X    { fprintf (stderr, "%3d:  <%3d,%3d,%3d> [%d]\n",
X           i, cmap[i].rd, cmap[i].gr, cmap[i].bl, cmap[i].indx);
X    }
X  }
X}
X
X/* Fast square macro, uses local variable to avoid mulitple eval of X */
X# define SQR(X) (sqrtmp = (X), sqrtmp*sqrtmp)
X
X/* Fast distance macro */
X# define CDIST(CPTR,CR,CG,CB)        \
X(sumtmp =  SQR (((int) ((CPTR)->rd)) - CR),        \
X sumtmp += SQR (((int) ((CPTR)->gr)) - CG),        \
X sumtmp += SQR (((int) ((CPTR)->bl)) - CB),        \
X sumtmp)
X
X# define restrict(X) ((X) < 0 ? 0 : (X) > 255 ? 255 : (X))
X
Xnearest (rd, gr, bl, cmap, colors)
Xint rd, gr, bl;
XCOLOR *cmap;
Xint colors;
X{ register int clr, sqrtmp, sumtmp;
X  register COLOR *a, *b, *c, *best, *ctail;
X  int cindx, bestd, dist;
X
X  rd = restrict (rd);
X  gr = restrict (gr);
X  bl = restrict (bl);
X
X  /* Find array index in cache */
X  cindx = CLRINDEX8 (rd, gr, bl);
X
X  /* Check cache for color value */
X  if ((clr = cache[cindx]) >= 0)
X  { return (clr); }
X
X  /*
X   * Search through colormap for nearest neighbor:
X   * 1) Find nearest red value by binary search
X   * 2) Search up and down, keeping best point
X   * 3) Terminate search when red difference is greater than best pt
X   */
X
X  /* Binary search for nearest red value */
X  ctail = &cmap[colors];
X  for (a=cmap, b= ctail-1;  a<b;  )
X  { c = a + (b-a)/2;    /* Find midpoint */
X
X    if (debug && verbose)
X    { fprintf (stderr, "Searching for %d, a=%d (%d), b=%d (%d), c=%d (%d)\n",
X        rd, a-cmap, a->rd, b-cmap, b->rd, c-cmap, c->rd);
X    }
X
X    if (c->rd == rd)
X    { break; }
X    else if (c->rd < rd)
X    { a = ++c; }
X    else
X    { b = c; }
X  }
X
X  /*
X   * c now points to closest red value, search up and down for closer
X   * Euclidean distance, and stop search when the red distance alone
X   * exceeds the bext found.
X   */
X
X  /* Set best and bestd to best red value */
X  best = c;
X  bestd = CDIST (c, rd, gr, bl);
X
X  if (debug && verbose)
X    fprintf (stderr, "Found c=%d (%d)  dist = %d\n", c-cmap, c->rd, bestd);
X
X  /* a and b are search pointers up and down */
X  a = c-1;
X  b = c+1;
X
X  while (bestd > 0 && (a >= cmap || b < ctail))
X  {
X    if (debug && verbose)
X    { fprintf (stderr, "  search: bestd %d, best %d|%d, a %d, b %d\n",
X        bestd, best-cmap, best->indx, a-cmap, b-cmap);
X    }
X
X    if (a >= cmap)
X    { if ((dist = CDIST (a, rd, gr, bl)) < bestd)
X      { best = a; bestd = dist; }
X
X      if (SQR ((int) a->rd - rd) >= bestd) a = cmap-1;
X      else                 a--;
X    }
X
X    if (b < ctail)
X    { if ((dist = CDIST (b, rd, gr, bl)) < bestd)
X      { best = b; bestd = dist; }
X
X      if (SQR ((int) b->rd - rd) >= bestd) b = ctail;
X      else                 b++;
X    }
X  }
X
X  if (best < cmap || best >= ctail)
X  { perror ("returning invalid color\n");
X    abort ();
X  }
X
X  clr = (best - cmap);
X
X  if (debug)
X  { fprintf (stderr, "Nearest(%3d,%3d,%3d) => <%3d,%3d,%3d> [%d]\n",
X        rd, gr, bl, best->rd, best->gr, best->bl, best->indx);
X  }
X
X  return ((cache[cindx] = clr));
X}
X
X/****************************************************************
X * sort colormap by decreasing red ( then green and blue )
X ****************************************************************/
X
Xcmp_cmap (a, b)
Xregister COLOR *a, *b;
X{ register int r;
X
X  if (r = (a->rd - b->rd)) { return (r); }
X  if (r = (a->gr - b->gr)) { return (r); }
X  if (r = (a->bl - b->bl)) { return (r); }
X
X  return (0);
X}
X
X/****************************************************************
X * sort colormap by increasing intensity (Use NTSC weights)
X ****************************************************************/
X
X# define RW 299
X# define GW 587
X# define BW 114
X
Xcmp_int (a, b)
Xregister COLOR *a, *b;
X{ register int ai, bi;
X
X  ai = RW * a->rd + GW * a->gr + BW * a->bl;
X  bi = RW * b->rd + GW * b->gr + BW * b->bl;
X
X  return (ai - bi);
X}
END_OF_FILE
if test 26110 -ne `wc -c <'fbquant.c'`; then
    echo shar: \"'fbquant.c'\" unpacked with wrong size!
fi
# end of 'fbquant.c'
fi
echo shar: End of archive 8 \(of 8\).
cp /dev/null ark8isdone
MISSING=""
for I in 1 2 3 4 5 6 7 8 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked all 8 archives.
    rm -f ark[1-9]isdone
else
    echo You still need to unpack the following archives:
    echo "        " ${MISSING}
fi
##  End of shell archive.
exit 0